For the design of circuits (e.g., digital or analog circuits) on the scale of VLSI (very large scale integration) technology, designers often employ computer aided techniques. Schematics and/or description languages have been used to describe the design of circuits (digital or analog). Standard languages such as Hardware Description Languages (HDLs) have been developed to describe digital circuits to aide in the design and simulation of complex digital circuits. Several hardware description languages, such as VHDL and Verilog, have evolved as industry standards. VHDL and Verilog are general purpose hardware description languages that allow definition of a hardware model at the gate level, the register transfer level (RTL) or the behavioral level using abstract data types. As device technology continues to advance, various product design tools have been developed to adapt HDLs for use with newer devices and design styles.
In designing an integrated circuit with an HDL code, the code is first written and then compiled by an HDL compiler. The HDL source code describes at some level the circuit elements, and the compiler produces an RTL netlist from this compilation. The RTL netlist is typically a technology independent netlist in that it is independent of the technology/architecture of a specific vendor's integrated circuit, such as field programmable gate arrays (FPGA) or an application-specific integrated circuit (ASIC). The RTL netlist corresponds to a schematic representation of circuit elements (as opposed to a behavioral representation). A mapping operation is then performed to convert from the technology independent RTL netlist to a technology specific netlist which can be used to create circuits in the vendor's technology/architecture. It is well known that FPGA vendors utilize different technology/architecture to implement logic circuits within their integrated circuits. Thus, the technology independent RTL netlist is mapped to create a netlist which is specific to a particular vendor's technology/architecture.
One operation, which is often desirable in this process, is to plan the layout of a particular integrated circuit and to control timing problems and to manage interconnections between regions of an integrated circuit. This is sometimes referred to as “floor planning.” A typical floor planning operation divides the circuit area of an integrated circuit into regions, sometimes called “blocks,” and then assigns logic to reside in a block. These regions may be rectangular or non-rectangular. This operation has two effects: the estimation error for the location of the logic is reduced from the size of the integrated circuit to the size of the block (which tends to reduce errors in timing estimates), and the placement and the routing typically runs faster because as it has been reduced from one very large problem into a series of simpler problems.
Logic partitioning is typically performed in the design of a digital circuit. Partitioning circuits enable one to apply divide-and-conquer techniques to simplify the design process (e.g., placement and routing). For example, a large digital circuit can be partitioned into portions so that each portion is implemented in an FPGA chip; and, the FPGA chips are interconnected by wire traces on a circuit board. Further, a digital circuit on a chip can be partitioned into regions on the chip, interconnected with chip wiring.
Partitioning algorithms have been developed to minimize the communication between partitions while ensuring that each portion is no larger than allowed (e.g., constrained by the capacity of an FPGA chip, or the area of a region on a chip). For example, U.S. Pat. No. 5,854,752 describes a method for partitioning a logic circuit for emulation under a virtual wires method using programmable logic devices. Many existing partitioning algorithms based on bipartitioning techniques, which find two partitions of a network of cells connected by nets such that the number of nets that connect the cells in both partitions is minimal. For example, the Fiduccia-Mattheyses algorithm (described in C. M. Fiduccia and R. M. Mattheyses, “A Linear-Time Heuristic for Improving Network Partitions”, Proceedings of the 19th Design Automation Conference, pp. 175-181, June 1982) is one of such bipartitioning techniques. A bipartitioning algorithm may be used repeatedly to partition a circuit into more than two partitions. Some multi-way partitioning techniques can also be found in the literature (e.g., Pak K. Chan, Martine D. F. Schlag, Jason Y. Zien, “Spectral-Based Multi-Way FPGA Partitioning”, Proceedings of the third international ACM symposium on Field-programmable gate arrays, p. 133-139, Feb. 12-14, 1995; George Karypis and Vipin Kumar, “Multilevel k-way Hypergraph Partitioning”, Proceedings of the 36th ACM/IEEE conference on Design automation conference, p. 343-348, Jun. 21-25, 1999).